#pragma once


#include "IncidenceGraph.h"


#include <map>
#include <list>
#include <algorithm>
#include <iostream>
using namespace std;


static const double INFINITY = numeric_limits<double>::infinity();


struct PathVertex
{
	int current;
	int previous;
	double distance;

	PathVertex() : current(-1), previous(-1), distance(INFINITY) { }
	PathVertex(int c, int p, double d) : current(c), previous(p), distance(d) {}
};


enum DijkstraStage
{
	NEXT_ITERATION,				// next iteration starts
	LAST_ITERATION,				// no more iterations to do
	FIND_SHORTEST_UNVISITED,	// find unvisited vertex with shortest distance
	VISIT_CONNECTED_EDGES,		// visit edges leaving from the current vertex
	UPDATE_DISTANCE,			// update distance of a connected vertex
};


typedef void (*DijkstraListener)
(
	int							iteration,
	DijkstraStage				stage,
	const map<int, PathVertex>*	paths,
	const map<int, bool>*		unvisited,
	int							current,
	int							neighborCount,
	int							neighbor,
	double						distanceToCurrent,
	double						oldDistanceToNeighbor,
	double						newDistanceToNeighbor
);


class Dijkstra
{
public:
	Dijkstra();
	~Dijkstra();

	bool CalculateShortestDistances(IncidenceGraph* graph, int source);

	list<PathVertex> GetShortestPath(int target);
	double GetDistance(int target);
	list<PathVertex> GetDistances();
	int GetPathCount();

	inline int Source() const { return source; }
	inline void Listener(DijkstraListener listener) { this->listener = listener; }

private:
	DijkstraListener listener;

	IncidenceGraph* graph;
	int source;

	map<int, PathVertex> shortestPaths;
};

